/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-200-岛屿数量
 * @date 2025/4/23 16:30
 */
public class Solution200 {
    public int numIslands(char[][] grid) {
        int ans = 0;
        int m = grid.length;
        int n = grid[0].length;

        // 遍历这个图中每个元素
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    // 当每次找到这个岛屿的一个点时(为1)，那么就以这个点开始出发，污染整个岛屿(置0)
                    ans++;
                    dfs(grid, i, j);
                }
            }
        }

        return ans;
    }

    private void dfs(char[][] grid, int i, int j) {
        int m = grid.length;
        int n = grid[0].length;

        if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == '0')
            return;

        // 依次开始污染上下左右4个点
        grid[i][j] = '0';
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
}